Euler's Totient Function

Definition

Euler's totient function \(\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\) is defined to be the number of positive integers less than or equal to \(n\) which are coprime to \(n\). That is

\[ \varphi(n) = |\{a \in \mathbb{Z}^+, a \leq n : \gcd(a, n) = 1\}|.\]

This function is useful in calculating the size of the multiplicative group of integers modulo n, and shows up in Euler's theorem, which is crucial to the design of RSA encryption.

The above formula is long and tedious when it comes to evaluating Euler's totient function, so we have the following results to simply calculations of it (with examples). We specifically have two results, which then lead to a generalisation at the bottom. This generalisation is the standard way of calculating the totient function.

Lemma

For a power of a prime number \(p\), \(\varphi(p^\alpha) = p^{\alpha} - p^{\alpha - 1} = p^{\alpha - 1}(p - 1)\).

Proof

Suppose \(p\) is a prime number and \(\alpha \geq 1\). An integer \(k\) satisfying \(0 < k \leq p^\alpha\) is coprime to \(p^\alpha\) if and only if \(p \not\mid k\), given that \(p^\alpha\) is only divisible by lower powers of \(p\) and \(p\) is prime. Hence, counting the cases when \(\gcd(k, p) > 1\), this is when \(p \mid k\) which happens for every \(p^{\text{th}}\) integer. Hence there are \(\frac{p^{\alpha}}{p} = p^{\alpha - 1}\) such integers, and hence \(p^\alpha - p^{\alpha - 1}\) which are not coprime to \(p^\alpha\).

Lemma

For \(a, b \in \mathbb{Z}^+\) with \(\gcd(a, b) = 1\),

\[ \varphi(ab) = \varphi(a) \cdot \varphi(b).\]

That is, \(\varphi\) is multiplicative.

Proof

This is actually just a simple corollary of the canonical decomposition of \(\mathbb{U}_n\), specifically we have that if \(a, b\) are coprime:

\[ \mathbb{U}_{ab} = \mathbb{U}_{a} \otimes \mathbb{U}_{b}.\]

Then we just take the size of each of these groups:

\[ \varphi(ab) = |\mathbb{U}_{ab}| = |\mathbb{U}_{a} \otimes \mathbb{U}_{b}| = |\mathbb{U}_{a}| \cdot |\mathbb{U}_{b}| = \varphi(a) \cdot \varphi(b).\]

Note that \(\mathbb{U}_n\) has \(\varphi(n)\) elements since an element \(a \in \mathbb{Z}_n\) is in \(\mathbb{U}_n\) if and only if it has a multiplicative inverse, which only happens for elements which are coprime to \(n\).

Theorem

For any \(n \in \mathbb{Z}^+\) with prime factorisation

\[ n = p_1^{\alpha_1} \cdot \dots \cdot p_k^{\alpha_k}\]

we have that

\[ \varphi(n) = n \prod_{i = 1}^k \left(1 - \frac{1}{p_i}\right).\]

Note that each term in the product of this last formula

\[ \varphi(n) = n \prod_{i = 1}^k \left(1 - \frac{1}{p_i}\right)\]

does not depend on the power of each prime, just the prime itself.

For example:

\[ \varphi(60) = 60\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right).\]
Proof

Let \(n = p_1^{\alpha_1} \cdot \dots \cdot p_k^{\alpha_k}\) as per the fundamental theorem of arithmetic.

Then, using multiplicativity and the formula for prime powers above we have that

\[\begin{align*} \varphi(n) &= \prod_{i = 1}^{k} \varphi(p_i^{\alpha_k}) \\ &= \prod_{i = 1}^{k} p_i^{\alpha_k} - p_i^{\alpha_k - 1} \\ &= \prod_{i = 1}^{k} p_i^{\alpha_{k}}\left(1 - \frac{1}{p_i}\right) \\ &= \left(\prod_{i = 1}^k p_i^{\alpha_k}\right) \left(\prod_{i = 1}^k \left(1 - \frac{1}{p_i}\right)\right) \\ &= n \prod_{i = 1}^k \left(1 - \frac{1}{p_i}\right). \\ \end{align*}\]